//  现在纸币面额有 1元，2元，5元，10元，20元，50元和100元，输入一个正整数的金额，输出所有的组成可能，比如输入 3元，则有  3个1元 和  一个2+1个1元两种可能;并统计组成的数量；
object MoneyCombination {
  val denominations = List(1, 2, 5, 10, 20, 50, 100)

  def findCombinations(target: Int): List[List[Int]] = {
    def backtrack(start: Int, currentSum: Int, currentCombination: List[Int]): List[List[Int]] = {
      if (currentSum == target) {
        List(currentCombination)
      } else if (currentSum > target) {
        List.empty
      } else {
        var allCombinations = List.empty[List[Int]]
        for (i <- start until denominations.length) {
          val newCombination = currentCombination :+ denominations(i)
          val nextCombinations = backtrack(i, currentSum + denominations(i), newCombination)
          allCombinations = allCombinations ++ nextCombinations
        }
        allCombinations
      }
    }

    backtrack(0, 0, List.empty)
  }

  def printCombinations(combinations: List[List[Int]]): Unit = {
    combinations.foreach { combination =>
      val counts = denominations.map { denom =>
        val count = combination.count(_ == denom)
        if (count > 0) s"$count 个$denom 元" else ""
      }.filter(_.nonEmpty).mkString(" + ")
      println(counts)
    }
  }

  def main(args: Array[String]): Unit = {
    import scala.io.StdIn
    println("请输入一个正整数金额:")
    val amount = StdIn.readInt()
    if (amount <= 0) {
      println("输入的金额必须是正整数。")
    } else {
      val combinations = findCombinations(amount)
      printCombinations(combinations)
      println(s"组成的数量为: ${combinations.length}")
    }
  }
}